package com.yxyu.sort.impl.input;

import com.yxyu.sort.SortBase;

/**
 * 插入排序
 * 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * @author yl
 */
public class InsertSort implements SortBase {

    @Override
    public String getName() {
        return "插入排序";
    }

    @Override
    public int[] sort(int[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < numbers[i - 1]) {
                //　小于前一个值，取当前值为坐标
                int temp = numbers[i];
                int j = i - 1;
                // 反向查找，进行插入
                for (; j >= 0; j--) {
                    if (temp < numbers[j]) {
                        // 大值向后移动一位
                        numbers[j + 1] = numbers[j];
                    } else {
                        // 碰到 <= 的值。结束回溯
                        break;
                    }
                }
                numbers[++ j] = temp;
            }
        }
        return numbers;
    }

}
